import java.util.ArrayList;
import java.util.List;

//面试题 01.04. 回文排列
class Solution {
    public boolean canPermutePalindrome(String s) {
        char[] ch=s.toCharArray();
        int[] arr=new int[95];
        int flag=0;
        for(int i=0;i<ch.length;i++){
            int x=ch[i]-32;
            arr[x]+=1;
        }
        for(int i=0;i<arr.length;i++){
            if(arr[i]%2==1){
                flag++;
            }
        }
        return flag<=1;
    }

}


//面试题 16.16. 部分排序
class Solution {
    public int[] subSort(int[] array) {
        int left=-1;
        int right=-1;
        int[] res=new int[2];
        //数组为空
        if(array.length==0){
            res[0]=left;
            res[1]=right;
            return res;
        }
        int max=array[0];
        int min=array[0];
        for(int i=0;i<array.length;i++){
            //记录最大值
            if(array[i]>max) {
                max=array[i];
            }
            //如果遇到递减,看是否为第一次,如果为第一次就记录该最小值
            if(array[i]<max&&min==array[0]) {
                min=array[i];
            }
            //不是第一次，看本次递减比上次递减是否要大
            else if((array[i]<max)&&(max-min)<(max-array[i])){
                min=array[i];
            }
            //每一次比记录的最大值小的都作为右边界，取最大的边界
            if(array[i]<max) right=i;
        }
        //求左边界
        for(int i=0;i<array.length;i++){
            //第一次比最小值小的作为左边界,并且right不等于-1，避免左边界比右边界大的情况
            if(array[i]>min&&right!=-1){
                left=i;
                break;
            }
        }
        res[0]=left;
        res[1]=right;
        return res;
    }
}


//118. 杨辉三角
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res=new ArrayList<>();
        for(int i=0;i<numRows;i++){
            List<Integer> temp=new ArrayList<>();
            for(int j=0;j<=i;j++){
                if(i==j||j==0){
                    temp.add(1);
                }
                else{
                    int k=res.get(res.size() - 1).get(j)+res.get(res.size() - 1).get(j-1);
                    temp.add(k);
                }
            }
            res.add(temp);
        }
        return res;
    }
}


//面试题 08.07. 无重复字符串的排列组合
class Solution {
    public String[] permutation(String S) {
        List<String> res=new ArrayList<>();
        //注意Boolean和boolean的区别
        boolean[] beUsed=new boolean[S.length()];
        //作为当前的组合
        StringBuilder cur=new StringBuilder();

        backTrack(S,res,beUsed,cur);

        //顺序表转String数组
        return res.toArray(new String[0]);
    }
    public void backTrack(String S,List<String> res,boolean[] beUsed,StringBuilder cur){
        if(cur.length()==S.length()){
            res.add(cur.toString());
            return;
        }
        for(int i=0;i<S.length();i++){
            if(beUsed[i]){
                continue;
            }

            beUsed[i]=true;
            cur.append(S.charAt(i));

            backTrack(S,res,beUsed,cur);

            beUsed[i]=false;
            cur.deleteCharAt(cur.length()-1);
        }
    }
}

